package com.zyk.grate_offer.class05;

import com.zyk.leetcode.TreeNode;
import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/5/7 21:20
 */
public class Code06_LeftRightSameTreeNumber {

    // 时间复杂度O(N*logN)
    // 最坏情况是完全二叉树(因为只有完全二叉树需要判断到底). 时间复杂度为 N + T(N) + 2T(N/2). 和归并排序的时间复杂度一样.
    // 由master公式推出时间复杂度O(N*logN)
    public static int sameNumber1(TreeNode root) {
        if (root == null) return 0;
        // 左树结果, 右树结果 + 当前左子树-右子树 是否相等
        return sameNumber1(root.left) + sameNumber1(root.right) + (same(root.left, root.right) ? 1 : 0);
    }

    private static boolean same(TreeNode left, TreeNode right) {
        if (left == null ^ right == null) {  // 一个true, 一个false.  异或结果为1也就是true
            return false;
        }
        if (left == null) return true;   // 这时候,它两个肯定都为null或都不为null, 如果都为null,返回true
        return left.val == right.val && same(left.left, right.left) && same(left.right, right.right);
    }


    public static int sameNumber2(TreeNode root) {
        if (root == null) return 0;
        // 左树结果, 右树结果 + 当前左子树-右子树 是否相等
        Hash hash = new Hash("MD5");
        return process(root, hash).num;
    }

    public static Info process(TreeNode root, Hash hash) {
        if (root == null) return new Info(0, hash.hash("#, "));
        Info lInfo = process(root.left, hash);
        Info rInfo = process(root.right, hash);
        int num = lInfo.num + rInfo.num + (lInfo.hash.equals(rInfo.hash) ? 1 : 0);
        String hashStr = hash.hash(root.val + lInfo.hash + rInfo.hash);
//        System.out.println(hashStr);
        return new Info(num, hashStr);
    }

    public static class Info {
        int num;        // 当前树上的答案
        String hash;    // 当前树的hash, 头+左+右

        public Info(int num, String hash) {
            this.num = num;
            this.hash = hash;
        }
    }


    public static void main(String[] args) {
//        System.out.println(true ^ false);
//        System.out.println(true ^ true);
//        System.out.println(false ^ false);

        Integer[] arr = {
                5, 1, 1, 2, 3, 2, 3
        };
        TreeNode root = TreeUtil.generateTreeByArr(arr);
        System.out.println(sameNumber1(root));
        System.out.println(sameNumber2(root));
    }

}
